package com.bjpowernode.util;

import java.util.ArrayList;
import java.util.List;

/*
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(returnMinStr("ADOBECODEBANC", "ABC"));
    }
    public static String returnMinStr(String s,String t){
        List<String> sList = strToList(s);
        List<String> tList = strToList(t);
        int index = 0;
        int length = 0;
        out:for (int i = tList.size(); i <= sList.size(); i++) {
            for (int j = 0; j <= sList.size()-i; j++) {
                List<String> newChar = new ArrayList<>();
                for (int k = j; k < j+i; k++) {
                    newChar.add(sList.get(k));
                }
                for (String ct : tList) {
                    newChar.remove(ct);
                }
                if (newChar.size()+tList.size() == i) {
                    index = j;
                    length = i;
                    break out;
                }
            }
        }
        if (index==0 && length==0)
            return "";
        return s.substring(index,index+length);
    }
    public static List<String> strToList(String str){
        List<String> strList = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            strList.add(str.substring(i,i+1));
        }
        return strList;
    }
}